package line;

/**
 * 线性表链式存储结构 内部类Node表示数据结点,包括一个指向下一节点next变量 变量header表示头结点 变量size
 * 
 * @author mengxin
 * @param <E>
 */
public class LinkedList<E> {
	private Node<E> header = null;// 头结点
	int size = 0;// 表示数组大小的指标

	/**
	 * 初始化头节点
	 */
	public LinkedList() {
		this.header = new Node<E>();
	}

	/**
	 * 增加元素
	 * 
	 * @param e
	 * @return
	 */
	public boolean add(E e) {
		if (size == 0) {
			header.e = e;
		} else {
			// 根据需要添加的内容，封装为结点
			Node<E> newNode = new Node<E>(e);
			// 得到当前最后一个结点
			Node<E> last = getNode(size - 1);
			// 在最后一个结点后加上新结点
			last.addNext(newNode);
		}
		size++;// 当前大小自增加1
		return true;
	}

	/**
	 * 向链表中插入元素
	 * 
	 * @param index
	 * @param e
	 * @return
	 */
	public boolean insert(int index, E e) {
		Node<E> newNode = new Node<E>(e);
		// 得到第N个结点
		Node<E> cNode = getNode(index);
		newNode.next = cNode.next;
		cNode.next = newNode;
		size++;
		return true;
	}

	/**
	 * 遍历当前链表，取得当前索引对应的元素
	 * 
	 * @return
	 */
	private Node<E> getNode(int index) {
		// 先判断索引正确性
		if (index > size || index < 0) {
			throw new RuntimeException("索引值有错：" + index);
		}
		Node<E> tem = new Node<E>();
		tem = header;
		int count = 0;
		while (count != index) {
			tem = tem.next;
			count++;
		}
		return tem;
	}
	
	private void deleteNode(int index){
		if (index > size || index < 0) {
			throw new RuntimeException("索引值有错：" + index);
		}
		Node<E> cNode = getNode(index-1);
		cNode.next = getNode(index+1);
		size--;
	}

	/**
	 * 根据索引，取得该索引下的数据
	 * 
	 * @param index
	 * @return
	 */
	public E get(int index) {
		// 先判断索引正确性
		if (index >= size || index < 0) {
			throw new RuntimeException("索引值有错：" + index);
		}
		Node<E> tem = new Node<E>();
		tem = header;
		int count = 0;
		while (count != index) {
			tem = tem.next;
			count++;
		}
		E e = tem.e;
		return e;
	}

	public int size() {
		return size;
	}

	/**
	 * 设置第index个结点的值
	 * @param x
	 * @param e
	 * @return
	 */
	public boolean set(int index, E e) {
		// 先判断索引正确性
		if (index > size || index < 0) {
			throw new RuntimeException("索引值有错：" + index);
		}
		Node<E> newNode = new Node<E>(e);
		// 得到第x个结点
		Node<E> cNode = getNode(index);
		cNode.e = e;
		return true;
	}

	@Override
	public String toString() {
		StringBuffer sb = new StringBuffer();
		sb.append("[");
		sb.append(this.header.getNode());
		sb.append("]");
		Node node = this.header.getNext();
		while(node!=null){
			sb.append("[");
			sb.append(node.getNode());
			sb.append("]");
			node = node.getNext();
		}
		return sb.toString();
	}

	/**
	 * 用来存放数据的结点型内部类
	 */
	class Node<E> {
		private E e;// 结点中存放的数据

		Node() {
		}

		Node(E e) {
			this.e = e;
		}

		Node<E> next;// 用来指向该结点的下一个结点

		/**
		 * 在此结点后加一个结点
		 * 
		 * @param node
		 */
		public void addNext(Node<E> node) {
			next = node;
		}
		
		public E getNode(){
			return this.e; 
		}
		
		public Node getNext(){
			return this.next;
		}
	}

	public static void main(String[] args) throws Exception {
		LinkedList<Integer> linked = new LinkedList<Integer>();
		for (int i = 0; i < 6; i++) {
			linked.add(i);
		}
		System.out.println(linked.toString());
		System.out.println("线性表当前元素数量"+linked.size());
		System.out.println("位置4数据"+linked.get(4));
		linked.set(3, 13);
		System.out.println("位置3更改后数据"+linked.get(3));
		linked.insert(3, 103);
		System.out.println(linked.toString());
		linked.deleteNode(3);
		System.out.println(linked.toString());
	}
}
